﻿#region using statements

using System;


#endregion

namespace XNAGameEngine.DataStructures
{
    /// <summary>
    /// <para>Heap data structure.</para>
    /// <para>Template parameter must implement interface IComparable</para>
    /// </summary>
    /// <typeparam name="T">heap object type</typeparam>
    public class Heap<T>
        where T : IComparable<T>
    {
        /// <summary>
        /// array containing all the values in the heap
        /// </summary>
        protected T[] _heapContents;

        /// <summary>
        /// Construct a new heap
        /// </summary>
        public Heap()
        {
            _heapContents = new T[16];
            Count = 0;
        }

        /// <summary>
        /// Get the number of objects stored in the heap
        /// </summary>
        public int Count
        {
            get;
            protected set;
        }

        /// <summary>
        /// Return the root item in the heap without removing it from the heap
        /// </summary>
        /// <returns>the root value in the heap</returns>
        public T Peek()
        {
            if (Count == 0)
                throw new Exception("no items in the heap");
            return _heapContents[1];
        }

        private void GrowHeap()
        {
            T[] newHeap = new T[Count * 2];
            Array.Copy(_heapContents, 1, newHeap, 1, Count - 1);
            _heapContents = newHeap;
        }

        /// <summary>
        /// Add an object to the heap
        /// </summary>
        /// <param name="value">the item to be added to the heap</param>
        public void Push(T value)
        {
            if (++Count == _heapContents.Length)
                GrowHeap();

            _heapContents[Count] = value;
            PercolateUp();
        }

        /// <summary>
        /// Remove and return the root item from the heap
        /// </summary>
        /// <returns>the root item</returns>
        public T Pop()
        {
            if (Count == 0)
                throw new Exception("no items in the heap");

            T returnValue = _heapContents[1];

            Count--;
            if (Count > 1)
            {
                _heapContents[1] = _heapContents[Count + 1];
                PercolateDown();
            }

            return returnValue;
        }

        /// <summary>
        /// Restores the heap-order property going up the tree, towards the root node
        /// </summary>
        protected void PercolateUp()
        {
            int currentIndex = Count;

            //while there is a parent to the current node and the child is larger than the parent
            while ((currentIndex != 1) &&
                    (_heapContents[currentIndex >> 1].CompareTo(
                        _heapContents[currentIndex]) == 1))
            {
                //swap the parent and child
                _heapContents[0] = _heapContents[currentIndex >> 1];
                _heapContents[currentIndex >> 1] = _heapContents[currentIndex];
                _heapContents[currentIndex] = _heapContents[0];

                //go up one level to next parent index
                currentIndex = currentIndex >> 1;
            }
        }

        /// <summary>
        /// Restores the heap-order property going down the tree, away from the root node
        /// </summary>
        protected void PercolateDown()
        {
            int currentIndex = 1;
            int childIndex;

            while (IsLeftChildSmaller(currentIndex)
                  || IsRightChildSmaller(currentIndex))
            {
                if (!CompareLeftChildToRight(currentIndex))
                    childIndex = (currentIndex << 1) + 1;
                else childIndex = currentIndex << 1;

                _heapContents[0] = _heapContents[childIndex];
                _heapContents[childIndex] = _heapContents[currentIndex];
                _heapContents[currentIndex] = _heapContents[0];
                currentIndex = childIndex;
            }
        }

        /// <summary>
        /// Returns whether the left child is smaller than the parent or false if this node
        /// is a leaf node
        /// </summary>
        /// <param name="parentIndex">the parent index to test</param>
        /// <returns>true if the left child is smaller than the parent, false otherwise</returns>
        protected bool IsLeftChildSmaller(int parentIndex)
        {
            if ((parentIndex << 1) >= Count - 1)
                return false;
            return
                _heapContents[parentIndex << 1].CompareTo(
                    _heapContents[parentIndex]) < 0;
        }

        /// <summary>
        /// Returns whether the right child is smaller than the parent or false if this node
        /// is a leaf node
        /// </summary>
        /// <param name="parentIndex">the parent index to test</param>
        /// <returns>true if the right child is smaller than the parent, false otherwise</returns>
        protected bool IsRightChildSmaller(int parentIndex)
        {
            if ((parentIndex << 1) + 1 >= Count - 1)
                return false;
            return
                _heapContents[(parentIndex << 1) + 1].CompareTo(
                    _heapContents[parentIndex]) < 0;
        }

        /// <summary>
        /// <para>Compares the child nodes</para>
        /// </summary>
        /// <param name="parentIndex">index of the parent to test</param>
        /// <returns>true if the left child is smaller or they are equal,
        /// false otherwise</returns>
        protected bool CompareLeftChildToRight(int parentIndex)
        {
            //both children are bigger or parentIndex is a leaf node
            if (IsLeftChildSmaller(parentIndex)
               && IsRightChildSmaller(parentIndex))
            {
                //find which child is smaller
                return _heapContents[parentIndex << 1].CompareTo(
                           _heapContents[(parentIndex << 1) + 1]) <= 0;
            }
            return IsLeftChildSmaller(parentIndex);
        }
    }
}